给你一个包含 n
个整数的数组 nums
,判断 nums
中是否存在三个元素 a
,b
,c
,使得 a + b + c = 0
?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
思路及算法
求三个数,满足相加为0
思路:先固定住一个数,然后使用双指针查找另外两个数
对原数组进行排序:
- 有效的过滤掉重复项
- 有利于双指针的进行
固定一个数
for i in range(len(nums)-2):
pass
因为排序的缘故,固定数是一组中的最小数,那么一旦固定数大于0
,则表示后续所有组合和均大于0
for i in range(len(nums)-2):
if nums[i] > 0:
break
如果当前固定数与前一个固定数相同,则可以跳过本轮计算
for i in range(len(nums)-2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
定义双指针
for i in range(len(nums)-2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
# 定义首尾双指针
left = i + 1
right = len(nums) - 1
和为0
for i in range(len(nums)-2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
# 定义首尾双指针
left = i + 1
right = len(nums) - 1
while left < right
sum = nums[left] + nums[right] + nums[i]
if sum == 0:
# 将当前索引新增至结果数组中
result.append(nums[i], nums[left], nums[right])
# 过滤重复项
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]
right -= 1
left += 1
right -= 1
和大于0
for i in range(len(nums)-2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
# 定义首尾双指针
left = i + 1
right = len(nums) - 1
while left < right
sum = nums[left] + nums[right] + nums[i]
if sum == 0:
# 将当前索引新增至结果数组中
result.append(nums[i], nums[left], nums[right])
# 过滤重复项
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]
right -= 1
left += 1
right -= 1
elif sum > 0:
# 因为单调递增,让sum减小则需要让right左移
right -= 1
和小于0
for i in range(len(nums)-2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
# 定义首尾双指针
left = i + 1
right = len(nums) - 1
while left < right
sum = nums[left] + nums[right] + nums[i]
if sum == 0:
# 将当前索引新增至结果数组中
result.append(nums[i], nums[left], nums[right])
# 过滤重复项
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]
right -= 1
left += 1
right -= 1
elif sum > 0:
# 因为单调递增,让sum减小则需要让right左移
right -= 1
else:
# 与大于的情况相反
left += 1
完整代码
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
length = len(nums)
result = []
if length < 3:
return result
for i in range(length-2):
# 如果最小值都是大于0,那么直接退出循环
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
left = i + 1
right = length - 1
while left < right:
sum = nums[left] + nums[right] + nums[i]
if sum == 0:
result.append([nums[left], nums[right], nums[i]])
# 过滤掉重复
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] = nums[right-1]:
right -= 1
right -= 1
left += 1
elif sum > 0:
right -= 1
else:
left += 1
return result